package com.explorati.LeetCode216.combinationSum3;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @ Author : Weijian_Wang
 * @ Date : Created in 18:55 2020/10/5 0005
 * @ Description ：
 */
public class Solution {

    /**
     * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
     *
     * 输入: k = 3, n = 7
     * 输出: [[1,2,4]]
     * @param k
     * @param n
     * @return
     */
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        //优化1 当target > 45(1+2+..+9) 时， 直接返回空
        if(k <= 0 || n <= 0 || n > 45) {
            return res;
        }

        findCombinations(k, 1, n, new ArrayDeque());

        return res;
    }

    private void findCombinations(int k, int index, int target, Deque preList) {
        if(preList.size() == k && target == 0) {
            res.add(new ArrayList<>(preList));
            return;
        }

        for(int i = index; i <= 9; i++) {
            if(target - i >= 0) {
                preList.add(i);
                findCombinations(k, i +1,target - i, preList);
                preList.removeLast();
            }else {
                break;
            }
        }
    }
}
